package com.nav.util;

import java.math.BigInteger;
import java.util.Date;

public class AdvancedMath {
	public static long GCD(long n1, long n2) {
		return GCDmm(java.lang.Math.min(n1, n2), java.lang.Math.max(n1, n2));
	}
	public static int GCD(int n1, int n2) {
		return GCDmm(java.lang.Math.min(n1, n2), java.lang.Math.max(n1, n2));
	}
	private static long GCDmm(long m, long M) {
		if(m == 0)
			return M;
		return GCDmm(M % m, m);
	}
	private static int GCDmm(int m, int M) {
		if(m == 0)
			return M;
		return GCDmm(M % m, m);
	}
	public static double pow(double a, long b) {
		double c = 1;
		long m = 0x8000;
		while(m > 0) {
			c *= c;
			if((b & m) > 0)
				c *= a;
			m = m >> 1;
		}
		return c;
	}
	/**
	 * Computes (base ^ exponent) % modulus
	 * @param base
	 * @param exponent
	 * @param modulus
	 * @return (base ^ exponent) % modulus
	 */
	public static int pow(BigInteger base, BigInteger exponent, int modulus) {
	    long b = base.mod(new BigInteger(Integer.toString(modulus))).longValue();
	    int result = 1;
	    while (exponent.compareTo(BigInteger.ZERO) > 0) {
	       if (exponent.testBit(0))
	           result = (int)((result * b) % modulus);
	       b = (b * b) % modulus;
	       exponent = exponent.shiftRight(1);
	    }
	    return result;
	}
	/**
	 * @param n number between 1 and 20
	 * @return product of natural numbers from 1 till n if n >= 1, 0 otherwise
	 * If n > 12 returned value doesn't fit in integer
	 * If n > 20 returned value is unexpected as the product doesn't fit in long
	 */
	public static long pi(int n) {
		if(n <= 0)
			return 0;
		long ret = 1;
		for(long i = 2; i <= n; i++)
			ret *= i;
		return ret;
	}
	/**
	 * @param n number between -65535 and 65535
	 * @return sum of natural numbers from 0 till n
	 * If n > 65535 or n < -65535 returned value is unexpected as the sum doesn't fit in integer
	 */
	public static int sigma(int n) {
		if(n < 0)
			return -sigma(-n);
		int ret = 0;
		for(int i = 1; i <= n; i++)
			ret += i;
		return ret;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		double a = 1234;
		long b = 12;
		
		long t1 = new Date().getTime();
		System.out.println(java.lang.Math.pow(a, b));
		long t2 = new Date().getTime();
		System.out.println("java: " + (t2 - t1));
		
		t1 = new Date().getTime();
		System.out.println(Math.pow(a, b));
		t2 = new Date().getTime();
		System.out.println("nav: " + (t2 - t1));
		
		System.out.println(pi(20));
		System.out.println(sigma(65535));
		System.out.println((java.lang.Math.sqrt(1l + 8l * (long)Integer.MAX_VALUE) - 1l) / 2l);
	}
}
